<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
  <head>
    <title>COMP332 2012 Assignment Three</title>
  </head>

  <body>
    <h1>Macquarie University<br>Department of Computing</h1>

    <h2>COMP332 Programming Languages 2012</h2>

    <h2>Assignment Three</h2>

    <h3>MiniJava Translation to the Java Virtual Machine</h3>

    <p>Due: 11am Monday 5 November (Week 13)<br>
      Worth: 10%</p>

    <p>This assignment asks you to finish the MiniJava implementation we
    started in the first two assignments by implementing translation
    from MiniJava source constructs to Java Virtual Machine class files.
    By the end of this assignment you will have a working MiniJava compiler
    and wil be able to produce class files that can be run on the Java
    Virtual Machine.</p>

    <p>The assignment uses the syntax and semantic analysis phases from
    the first two assignments with some minor changes (described below).
    The translation and code generation
    scheme is heavily based on that used in the practical exercises for
    weeks 9 and 10. If you have not completed those exercises, we strongly
    encourage you to do so before starting work on this assignment. In
    many cases, the work required here is the same or very similar to
    that required in the practical exercises. You should also make sure
    that you have read the "Translation and Code Generation" lecture
    notes from week 9 since they give an overview of the processes
    you will need to implement.</p>

    <h4>Updates from Assignment Two</h4>

    <p>The semantic analysis from Assignment Two did not distinguish
    between the entities that represent instance variables (fields
    declared inside a class but outside all methods) and local
    variables (those declared inside a method). To do translation
    properly we need to make this distinction since the JVM uses
    different operations to access fields and to access local
    variables. Thus, the semantic analysis phases from Assignment
    Two has been extended to add a new <code>FieldEntity</code>
    which is used to represent fields. <code>VariableEntity</code>
    is only used for local variables now.</p>

    <p>Also, note that the semantic analysis phase from Assignment
    Two does not deal properly with classes whose names are used
    either before the declaration of the class, or within the class
    itself. Ultimately, it would be best to support these structures,
    but for the purposes of this unit, we will just assume that
    classes are defined before they are used. For this reason, we
    have removed the <code>treevisitor.java</code> example since
    it has a class that refers to itself. Some other examples have
    been changed to reorder the class definitions so that they
    work with the restriction.</p>

    <h4>What you have to do</h4>

    <p>You have to write, document and test a Scala translator
    for the MiniJava language to the Java virtual machine.
    Your translator should support all of the features of the
    MiniJava language and translate them to equivalent JVM
    operations.</p>

    <p>A skeleton sbt project for the assignment has been provided
    on BitBucket as the <code>inkytonik/comp332-ass3</code> repository.
    The skeleton implements quite a lot of the translation for you.
    Look for FIXME to find places where you have to extend the
    skeleton.</p>

    <p>There is only one part in this assignment. Within that
    part it is advisable to solve small portions at a time rather
    than trying to code the whole solution in one go.
    As a first step you should consider working on simple
    expressions and use the <code>Println</code> statement in a
    MiniJava main class to print out the expression values for
    testing. Translation of <code>Println</code> statements has
    already been done for you in the skeleton.</p>

    <p>We have not provided an automated testing setup for this
    assignment, because the main tests would be to compile real
    programs and run them to make sure that they do what they
    are supposed to do. This is hard to automate using our previous
    techniques. You will probably find it useful to write scripts
    to run your compiler, use Jasmin to convert the resulting
    <code>.j</code> files into <code>.class</code> files and
    then use the <code>java</code> command to run the relevant
    main class. To help with testing, the <code>test/*.exp</code>
    files contain the expected output when you run the different
    test programs.</p>

    <h4>MiniJava translation and code generation</h4>

    <p>The assignment skeleton contains the outline of a translator
    (in <code>Translator.scala</code>) and the implementation of a
    code generator (in <code>CodeGenerator.scala</code>). You should
    <em>not</em> have to modify the code generator to complete this
    assignment. Just finish the implementation of the translator.</p>

    <p>The skeleton translator contains much of the code you will
    need. In particular, the skeleton already knows how to translate
    classes and methods into the JVM tree representation. Your
    focus will be to implement <code>translateStmt</code> and
    <code>translateExp</code> which translate statements and
    expressions, respectively.</p>

    <p>As in the practical exercises for the expression language, you
    will build trees that represent the class files that you want to
    generate. The structure of those trees is defined in
    <code>JVMTree.scala</code>. The skeleton contains definitions
    for many of the JVM operations in the JVM tree definition (see
    the section labelled "JVM instructions"). You may want to add
    more instructions, if the operations you want to use are not
    already present. Follow the explanation in the code to add new
    instructions.</p>

    <p>You may also find it useful to use the Java compiler to help
    you work out the appropriate operations to use. For example,
    you can write simple Java programs, compile them with the
    <code>javac</code> compiler and then use the <code>javap -c</code>
    command to look at the class file(s) and the instructions that
    are produced by the Java compiler.</p>

    <p>To see the full range of operations that are available on the
    JVM, consult the Java virtual machine specification, particularly
    the section labelled "Instruction Set Summary", "The Java
    Virtual Machine Instruction Set" and "Compiling for the Java
    Virtual Machine". Bear in mind that many JVM operations are not
    needed for the simple MiniJava language, particularly those
    dealing with floating-point numbers and exceptions.</p>

    <p>The following useful links point to the documentation for Java 5,
    which should be sufficient for this assignment. We would not expect
    that you will need to read all of this documentation, but it will
    probably be useful as a reference, particularly the instruction
    set information, if you are unsure about what an instruction does.</p>

    <ul>
        <li><a href="http://docs.oracle.com/javase/specs/jvms/se5.0/html/VMSpecTOC.doc.html">JVM specification: http://docs.oracle.com/javase/specs/jvms/se5.0/html/VMSpecTOC.doc.html</a></li>
        <li><a href="http://docs.oracle.com/javase/specs/jvms/se5.0/html/Overview.doc.html#7143">JVM instruction set summary: http://docs.oracle.com/javase/specs/jvms/se5.0/html/Overview.doc.html#7143</a></li>
        <li><a href="http://docs.oracle.com/javase/specs/jvms/se5.0/html/Instructions.doc.html">JVM instruction set detail: http://docs.oracle.com/javase/specs/jvms/se5.0/html/Instructions.doc.html</a></li>
        <li><a href="http://docs.oracle.com/javase/specs/jvms/se5.0/html/Compiling.doc.html">Compiling for the Java virtual machine: http://docs.oracle.com/javase/specs/jvms/se5.0/html/Compiling.doc.html</a></li>
    </ul>

    <p>For examples on the type of code that you might generate, consult the
    lecture notes "Translation and Code Generation" (week 9) and the "Compiling
    for the Java Virtual Machine" link above which both contain
    examples. Part of this assignment is to explore the JVM, so you
    may need more features of the JVM than are covered in the lecture notes.
    Use the documentation above or other resources you can find on the net
    to explore this space. In most cases, the JVM has operations that directly
    correspond to the MiniJava source constructs, so the code that you
    generate should be quite simple.</p>

    <p>As an example, consider the generation of code for a plus expression.
    We need to generate the translations of the two operands of the expression.
    That JVM code will leave those two values on the top of the operand stack.
    Thus, we only need to append an <code>iadd</code> instruction to add
    them together and leave the result on the stack instead. The translator
    code in <code>translateExp</code> for this case looks like this:</p>

<pre>
case PlusExp (left, right) =>
    translateExp (left)
    translateExp (right)
    gen (Iadd ())
</pre>

    <p>As a more complex example, consider generating code for a less
    expression whose value is assigned to a Boolean variable. E.g.,
    MiniJava code like this: <code>b := i1 &lt; i2</code> where <code>b</code>
    is a Boolean variable and the other two variables are integers.
    Here is the translation code that first evaluates the two operands,
    then uses a conditional branch to jump to either code that pushes
    a one value (for true) or a zero value (for false). This code also
    illustrates using the <code>makeLabel</code> method to generate
    unique labels.</p>

<pre>
case LessExp (left, right) =>
    val label1 = makeLabel ()
    val label2 = makeLabel ()
    translateExp (left)
    translateExp (right)
    gen (If_icmpge (label1))
    gen (Iconst_1 ())
    gen (Goto (label2))
    gen (Label (label1))
    gen (Iconst_0 ())
    gen (Label (label2))
</pre>

    <p>Similarly simple schemes can be used to translate all of the
    MiniJava constructs. The following notes provide some guidance
    for the translation schemes or special cases. The skeleton also
    contains some comments to guide your coding.</p>

    <ol>
        <li><p>The and operation needs to be short-circuited, so you will
        have to use a scheme to make sure that the right operand is
        not evaluated if the left operand is false.</p></li>

        <li><p>The JVM has quite a few operations for dealing with arrays
        directly, including operations for loading and storing from integer
        arrays, and for calculating the length of an array. It also has
        operations for dealing with arrays whose elements are references,
        but these are not needed for MiniJava.</p></li>

        <li><p>The JVM doesn't really have operations on Boolean values,
        so you should use integers to represent Boolean. Choose
        zero for false and one for true.</p></li>

        <li><p>To call a (virtual) method, we must first push the object
        on which the call is being made, then we push the actual argument
        values in the order of their declaration, and then we use the
        <code>invokevirtual</code> instruction passing a method specification
        that specifies the method that we want to call.</p></li>

        <li><p>A method specification identifies a particular method b
        giving its class, name, list of argument types and return type.
        See the translation of the <code>println</code> statements for
        an example of how to construct a method specification.</p></li>

        <li><p>When a virtual method body is being executed, the first local
        variable slot (number 0) holds the reference to the object on which
        the call is being made. If the method has <em>n</em> arguments, then
        the local variable slots 1 to <em>n</em> hold the values of the
        arguments in the order of the declaration. After the arguments in
        slots <em>n + 1</em> and following come any other local variables
        that the method has.</p></li>

        <li><p>There are a few instructions for returning from methods:
        one for returning an integer (<code>ireturn</code>), one for
        returning an object or array reference (<code>areturn</code>),
        and one for returning from a void method (<code>return</code>).</p></li>
    </ol>

<h4>What you must hand in and how</h4>

<ol>

    <li> <p>All of the code for your compiler. To make this
    clear, submit <em>every file</em> that is needed to build your
    program from source, including files in the skeleton that you have
    not changed. Do not add any new files or include multiple versions
    of your files. Do not include any libraries. We will compile all
    of the files that you submit using sbt, so you should avoid any
    other build mechanisms.</p></li>

    <li><p>Your submission should include all of the tests that you have
    used to make sure that your program is working correctly. Note
    that just testing one or two simple cases is not enough for many
    marks. You should test as comprehensively as you can.</p></li>

     <li> <p>A type-written report that describes how you have
     achieved the goals of the assignment. Your report must contain
     the following components or sections:</p></li>

      <ul>

      <li>A title page or heading that gives the assignment details,
      your name and student number.</li>

      <li>A brief introduction that summarises the aim of the
     assignment and the structure of the rest of the report.</li>

      <li>A description of the design and implementation work that you
      have done to achieve the goals of the assignment. Listing some
      code fragments may be useful to illustrate your description, but
      don't just give a long listing. Leaving out obvious stuff is OK,
      as long as what you have done is clear. A good rule of thumb is
      to include enough detail to allow a student to understand it if
      they are at the stage you were at when you started work on the
      assignment.</li>

     <li>A description of the testing that you carried out. You should
     demonstrate that you have used a properly representative set of
     test cases to be confident that you have covered all the bases.
     Include details of the tests that you used and the rationale
     behind why they were chosen. Do not just print the tests out
     without explanation.</li>

    </ul>

</ol>

<p>Submit your code and report electronically as a single zip file
called <code>ass3.zip</code> using the appropriate submission link on
the COMP332 iLearn website by the due date and time. Your report
should be in PDF format. DO NOT SUBMIT YOUR ASSIGNMENT OR DOCUMENTATION
IN ANY OTHER FORMAT THAN ZIP and PDF, RESPECTIVELY.</p>

<h4>Marking</h4>

<p>The assignment will be assessed according to the assessment
standards for Learning Outcomes 2, 3 and 4 as specified in the Unit
Guide.</p>

<p>Marks will be allocated equally to the code and to the report. Your
code will be assessed for correctness and quality with respect to the
assignment description. Marking of the report will assess the clarity
and accuracy of your description and the adequacy of your testing.
Marks allocated to testing will be 30% of the marks for the
assignment.</p>

    <hr>
    <address><a href="mailto:Anthony.Sloane@mq.edu.au">Tony Sloane</a></address>
<br>
<a href="http://www.mq.edu.au/legalstuff.html">Copyright (c) 2012-2015 by
Anthony Sloane, Macquarie University. All rights reserved.</A></FONT><BR>
  </body>
</html>
